#include "opt.hh"
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <climits>
using namespace twlm::ccpl::modules;

void TACOptimizer::warning(const std::string &module, const std::string &msg) const
{
    std::cerr << "AST Opt[" << module << "] Warning: " << msg << std::endl;
}

std::shared_ptr<SYM> TACOptimizer::make_const(int value) const
{
    auto const_sym = std::make_shared<SYM>();
    const_sym->type = SYM_TYPE::CONST_INT;
    const_sym->value = value;
    const_sym->data_type = DATA_TYPE::INT;
    return const_sym;
}

// 局部常量折叠（只处理立即数常量）
bool TACOptimizer::local_constant_folding(std::shared_ptr<TAC> tac,std::shared_ptr<TAC> end)
{
    bool changed = false;
    auto current = tac;

    while (current != nullptr)
    {
        // 二元运算
        if (current->op == TAC_OP::ADD || current->op == TAC_OP::SUB ||
            current->op == TAC_OP::MUL || current->op == TAC_OP::DIV)
        {
            int val_b, val_c;
            if (current->b->get_const_value(val_b) &&
                current->c->get_const_value(val_c))
            {
                int result = 0;
                bool valid = true;

                switch (current->op)
                {
                case TAC_OP::ADD:
                    result = val_b + val_c;
                    break;
                case TAC_OP::SUB:
                    result = val_b - val_c;
                    break;
                case TAC_OP::MUL:
                    result = val_b * val_c;
                    break;
                case TAC_OP::DIV:
                    if (val_c != 0)
                    {
                        result = val_b / val_c;
                    }
                    else
                    {
                        valid = false;
                        warning("Constant Folding", "Division by zero!!!");
                    }
                    break;
                default:
                    valid = false;
                    break;
                }

                if (valid)
                {
                    current->op = TAC_OP::COPY;
                    current->b = make_const(result);
                    current->c = nullptr;
                    changed = true;
                }
            }
        }
        // 比较运算
        else if (current->op == TAC_OP::EQ || current->op == TAC_OP::NE ||
                 current->op == TAC_OP::LT || current->op == TAC_OP::LE ||
                 current->op == TAC_OP::GT || current->op == TAC_OP::GE)
        {
            int val_b, val_c;
            if (current->b->get_const_value(val_b) &&
                current->c->get_const_value(val_c))
            {
                int result = 0;

                switch (current->op)
                {
                case TAC_OP::EQ:
                    result = (val_b == val_c) ? 1 : 0;
                    break;
                case TAC_OP::NE:
                    result = (val_b != val_c) ? 1 : 0;
                    break;
                case TAC_OP::LT:
                    result = (val_b < val_c) ? 1 : 0;
                    break;
                case TAC_OP::LE:
                    result = (val_b <= val_c) ? 1 : 0;
                    break;
                case TAC_OP::GT:
                    result = (val_b > val_c) ? 1 : 0;
                    break;
                case TAC_OP::GE:
                    result = (val_b >= val_c) ? 1 : 0;
                    break;
                default:
                    break;
                }

                current->op = TAC_OP::COPY;
                current->b = make_const(result);
                current->c = nullptr;
                changed = true;
            }
        }
        // 处理一元运算（NEG）
        else if (current->op == TAC_OP::NEG)
        {
            int val_b;
            if (current->b->get_const_value(val_b))
            {
                current->op = TAC_OP::COPY;
                current->b = make_const(-val_b);
                current->c = nullptr;
                changed = true;
            }
        }
        if(current==end)
            break;
        current = current->next;
    }

    return changed;
}

// 局部拷贝传播
bool TACOptimizer::local_copy_propagation(std::shared_ptr<TAC> tac,std::shared_ptr<TAC> end)
{
    bool changed = false;
    std::unordered_map<std::shared_ptr<SYM>, std::shared_ptr<SYM>> copy_map;

    auto current = tac;
    while (current != nullptr)
    {
        // 处理简单的拷贝赋值 a = b（b不是常量）
        if (current->op == TAC_OP::COPY && current->a && current->b &&
            current->b->type == SYM_TYPE::VAR)
        {
            copy_map[current->a] = current->b;
        }
        // 如果变量被重新赋值，清除其拷贝信息
        else if (current->a)
        {
            copy_map.erase(current->a);
        }

        // 替换使用处
        bool is_pointer_op = (current->op == TAC_OP::ADDR || 
                              current->op == TAC_OP::LOAD_PTR || 
                              current->op == TAC_OP::STORE_PTR);

        if (current->b && current->b->type == SYM_TYPE::VAR && !is_pointer_op)
        {
            auto it = copy_map.find(current->b);
            if (it != copy_map.end())
            {
                current->b = it->second;
                changed = true;
            }
        }

        if (current->c && current->c->type == SYM_TYPE::VAR && !is_pointer_op)
        {
            auto it = copy_map.find(current->c);
            if (it != copy_map.end())
            {
                current->c = it->second;
                changed = true;
            }
        }

        if(current==end)
            break;
        current = current->next;
    }

    return changed;
}

// 局部二元交换（利用群交换律）
bool TACOptimizer::local_binary_swapping(std::shared_ptr<TAC> tac,std::shared_ptr<TAC> end){
    // a= const + b -> a= b + const, make it easier for constant folding and other optimizations
    bool changed=false;
    auto current = tac;
    while (current != nullptr)
    {
        if ((current->op == TAC_OP::ADD || current->op == TAC_OP::MUL) &&
            current->b && current->c &&
            (current->b->type == SYM_TYPE::CONST_INT && current->c->type == SYM_TYPE::VAR))
        {
            // Swap operands
            std::swap(current->b, current->c);
            changed = true;
        }
        if(current==end)
            break;
        current = current->next;
    }
    return changed;
}

// 局部链式表达式折叠
bool TACOptimizer::local_chain_folding(std::shared_ptr<TAC> tac,std::shared_ptr<TAC> end){
    // e=a+b+c+d;假设a是变量，b,c,d是常量，TAC链由于a未知，整个链将在运行时计算。但是b+c+d是可以根据加法结合律提前运算的。
    // 查找形如 t1=a+const1; t2=t1+const2; ... 的链式加法表达式，并将常量部分提前计算
    bool changed = false;
    
    // 记录每个变量的定义：变量 -> (操作类型, 操作数1, 操作数2)
    struct DefInfo {
        TAC_OP op;
        std::shared_ptr<SYM> left;   // 左操作数
        std::shared_ptr<SYM> right;  // 右操作数
        std::shared_ptr<TAC> tac;    // 定义该变量的TAC指令
    };
    
    std::unordered_map<std::shared_ptr<SYM>, DefInfo> def_map;
    
    auto current = tac;
    while (current != nullptr)
    {
        // 只处理加法和减法（可以应用结合律）
        if ((current->op == TAC_OP::ADD || current->op == TAC_OP::SUB) && 
            current->a && current->b && current->c)
        {
            // 记录定义信息
            def_map[current->a] = {current->op, current->b, current->c, current};
            
            // 检查是否形成链：t2 = t1 + const 或 t2 = t1 - const
            // 其中 t1 = var + const 或 t1 = var - const
            
            // 情况1: t2 = t1 op2 const2，其中 t1 = var op1 const1
            if (current->b->type == SYM_TYPE::VAR)
            {
                auto it = def_map.find(current->b);
                if (it != def_map.end())
                {
                    const auto& def = it->second;
                    
                    // 检查链条：左操作数是变量定义，右操作数是常量
                    int const1, const2;
                    bool left_has_const = def.right && def.right->get_const_value(const1);
                    bool right_is_const = current->c->get_const_value(const2);
                    
                    // t1 = var op1 const1; t2 = t1 op2 const2
                    // 可以转换为: t2 = var op1 (const1 op2' const2)
                    if (left_has_const && right_is_const && 
                        def.left && def.left->type == SYM_TYPE::VAR)
                    {
                        int combined_const = 0;
                        TAC_OP new_op = def.op;
                        
                        // 计算合并后的常量
                        if (def.op == TAC_OP::ADD && current->op == TAC_OP::ADD)
                        {
                            // var + c1 + c2 = var + (c1+c2)
                            combined_const = const1 + const2;
                            new_op = TAC_OP::ADD;
                        }
                        else if (def.op == TAC_OP::ADD && current->op == TAC_OP::SUB)
                        {
                            // var + c1 - c2 = var + (c1-c2)
                            combined_const = const1 - const2;
                            new_op = TAC_OP::ADD;
                        }
                        else if (def.op == TAC_OP::SUB && current->op == TAC_OP::ADD)
                        {
                            // var - c1 + c2 = var - (c1-c2) 或 var + (c2-c1)
                            combined_const = const2 - const1;
                            new_op = TAC_OP::ADD;
                        }
                        else if (def.op == TAC_OP::SUB && current->op == TAC_OP::SUB)
                        {
                            // var - c1 - c2 = var - (c1+c2)
                            combined_const = const1 + const2;
                            new_op = TAC_OP::SUB;
                        }
                        
                        // 如果合并后的常量为负数且操作是ADD，转换为SUB
                        if (new_op == TAC_OP::ADD && combined_const < 0)
                        {
                            new_op = TAC_OP::SUB;
                            combined_const = -combined_const;
                        }
                        else if (new_op == TAC_OP::SUB && combined_const < 0)
                        {
                            new_op = TAC_OP::ADD;
                            combined_const = -combined_const;
                        }
                        
                        // 应用优化：直接使用原始变量和合并后的常量
                        current->op = new_op;
                        current->b = def.left;  // 使用链条起始的变量
                        current->c = make_const(combined_const);
                        
                        // 更新定义映射
                        def_map[current->a] = {new_op, def.left, current->c, current};
                        
                        changed = true;
                    }
                }
            }
            
            // 情况2: t2 = const2 op2 t1，其中 t1 = const1 op1 var (仅适用于加法交换律)
            if (current->op == TAC_OP::ADD && current->c->type == SYM_TYPE::VAR)
            {
                auto it = def_map.find(current->c);
                if (it != def_map.end())
                {
                    const auto& def = it->second;
                    
                    int const1, const2;
                    bool left_is_const = current->b->get_const_value(const2);
                    bool def_left_is_const = def.left && def.left->get_const_value(const1);
                    
                    // t1 = const1 + var; t2 = const2 + t1
                    if (def.op == TAC_OP::ADD && left_is_const && def_left_is_const &&
                        def.right && def.right->type == SYM_TYPE::VAR)
                    {
                        // const2 + (const1 + var) = (const1+const2) + var
                        int combined_const = const1 + const2;
                        
                        current->op = TAC_OP::ADD;
                        current->b = def.right;  // 使用原始变量
                        current->c = make_const(combined_const);
                        
                        def_map[current->a] = {TAC_OP::ADD, def.right, current->c, current};
                        
                        changed = true;
                    }
                }
            }
        }
        // 如果变量被重新定义，清除其定义信息
        else if (current->a && current->a->type == SYM_TYPE::VAR)
        {
            def_map.erase(current->a);
        }
        
        if (current == end)
            break;
        current = current->next;
    }
    
    return changed;
}

// 局部优化（基本块内）
void TACOptimizer::optimize_block_local(std::shared_ptr<BasicBlock> block)
{
    // 安全检查：确保块有有效的指令
    if (!block->start || !block->end)
    {
        return;
    }
    
    auto start = block->start;
    auto end = block->end;
    bool changed = true;
    int iter = 0;
    const int MAX_ITER = 20;

    while(changed && iter < MAX_ITER)
    {
        changed = false;
        iter++;

        if (local_constant_folding(start, end))
        {
            changed = true;
        }
        if (local_copy_propagation(start, end))
        {
            changed = true;
        }
        if(local_binary_swapping(start,end)){
            changed=true;
        }
        if(local_chain_folding(start,end))
        {
            changed = true;
        }
    }
}

// 全局常量传播（基于数据流分析）
bool TACOptimizer::global_constant_propagation(const std::vector<std::shared_ptr<BasicBlock>>& blocks)
{
    bool changed = false;
    const int BOTTOM = INT_MIN;
    const auto& block_in=block_builder.get_block_in();
    for (auto& block : blocks)
    {
        auto& in_constants = block_in.at(block).constants;
        auto current_constants = in_constants;
        
        auto tac = block->start;
        while (tac)
        {
            // 替换使用的变量为常量
            bool is_pointer_op = (tac->op == TAC_OP::ADDR || 
                                  tac->op == TAC_OP::LOAD_PTR || 
                                  tac->op == TAC_OP::STORE_PTR);
            
            if (tac->b && tac->b->type == SYM_TYPE::VAR && !is_pointer_op)
            {
                auto it = current_constants.find(tac->b);
                if (it != current_constants.end() && it->second != BOTTOM)
                {
                    tac->b = make_const(it->second);
                    changed = true;
                }
            }
            
            if (tac->c && tac->c->type == SYM_TYPE::VAR && !is_pointer_op)
            {
                auto it = current_constants.find(tac->c);
                if (it != current_constants.end() && it->second != BOTTOM)
                {
                    tac->c = make_const(it->second);
                    changed = true;
                }
            }
            
            // 特殊指令
            if (tac->op == TAC_OP::RETURN || tac->op == TAC_OP::OUTPUT ||
                tac->op == TAC_OP::IFZ || tac->op == TAC_OP::ACTUAL)
            {
                if (tac->a && tac->a->type == SYM_TYPE::VAR)
                {
                    auto it = current_constants.find(tac->a);
                    if (it != current_constants.end() && it->second != BOTTOM)
                    {
                        tac->a = make_const(it->second);
                        changed = true;
                    }
                }
            }
            
            // 更新当前常量状态
            auto def = tac->get_def();
            if (def)
            {
                // 简化计算
                if (tac->op == TAC_OP::COPY)
                {
                    int val;
                    if (tac->b->get_const_value(val))
                    {
                        current_constants[def] = val;
                    }
                    else
                    {
                        current_constants[def] = BOTTOM;
                    }
                }
                else
                {
                    current_constants[def] = BOTTOM;
                }
            }
            
            if (tac == block->end)
                break;
            tac = tac->next;
        }
    }
    
    return changed;
}

// 全局死代码消除（基于活跃变量分析）
bool TACOptimizer::global_dead_code_elimination(const std::vector<std::shared_ptr<BasicBlock>>& blocks)
{
    bool changed = false;
    const auto& block_out=block_builder.get_block_out();
    for (auto& block : blocks)
    {
        auto& out_live = block_out.at(block).live_vars;
        auto current_live = out_live;
        
        // 收集块内指令
        std::vector<std::shared_ptr<TAC>> instructions;
        auto tac = block->start;
        while (tac)
        {
            instructions.push_back(tac);
            if (tac == block->end)
                break;
            tac = tac->next;
        }
        
        // 逆序遍历，删除死代码
        for (auto it = instructions.rbegin(); it != instructions.rend(); ++it)
        {
            auto& instr = *it;
            auto def = instr->get_def();
            
            // 如果定义的变量不活跃，且指令没有副作用，可以删除
            if (def && current_live.find(def) == current_live.end())
            {
                // 检查是否有副作用（CALL, INPUT 等不能删除）
                if (instr->op != TAC_OP::CALL && instr->op != TAC_OP::INPUT &&
                    instr->op != TAC_OP::LOAD_PTR && instr->op != TAC_OP::STORE_PTR)
                {
                    // 保存指针后删除该指令
                    auto instr_prev = instr->prev;
                    auto instr_next = instr->next;
                    
                    if (instr_prev)
                    {
                        instr_prev->next = instr_next;
                    }
                    if (instr_next)
                    {
                        instr_next->prev = instr_prev;
                    }
                    
                    // 更新块的起始或结束指针
                    if (instr == block->start)
                    {
                        block->start = instr_next;
                    }
                    if (instr == block->end)
                    {
                        block->end = instr_prev;
                    }
                    
                    // 清空被删除指令的链接
                    instr->prev = nullptr;
                    instr->next = nullptr;
                    
                    changed = true;
                    continue;
                }
            }
            
            // 更新活跃变量集合
            if (def)
            {
                current_live.erase(def);
            }
            
            auto uses = instr->get_uses();
            for (auto& use : uses)
            {
                current_live.insert(use);
            }
        }
    }
    
    return changed;
}

// 判断是否是循环头
bool TACOptimizer::is_loop_header(std::shared_ptr<BasicBlock> block) const
{
    // 循环头的特征：有前驱在它之后（回边）
    for (const auto& pred : block->predecessors)
    {
        if (pred->id >= block->id)  // 简单判断：后继块指向前面的块
        {
            return true;
        }
    }
    return false;
}

// 查找循环体中的所有基本块
void TACOptimizer::find_loop_blocks(std::shared_ptr<BasicBlock> header,
                                    std::unordered_set<std::shared_ptr<BasicBlock>>& loop_blocks) const
{
    loop_blocks.clear();
    loop_blocks.insert(header);
    
    // 使用工作列表算法，从回边的源节点开始反向遍历
    std::queue<std::shared_ptr<BasicBlock>> worklist;
    
    for (const auto& pred : header->predecessors)
    {
        if (pred->id >= header->id)  // 回边
        {
            worklist.push(pred);
            loop_blocks.insert(pred);
        }
    }
    
    while (!worklist.empty())
    {
        auto block = worklist.front();
        worklist.pop();
        
        for (const auto& pred : block->predecessors)
        {
            if (loop_blocks.find(pred) == loop_blocks.end())
            {
                loop_blocks.insert(pred);
                worklist.push(pred);
            }
        }
    }
}

// 获取表达式的唯一键（用于CSE）
std::string TACOptimizer::get_expression_key(std::shared_ptr<TAC> tac) const
{
    if (!tac)
        return "";
    
    std::string key;
    
    switch (tac->op)
    {
    case TAC_OP::ADD:
    case TAC_OP::MUL:  // 交换律
        {
            std::string b_str = tac->b ? tac->b->to_string() : "";
            std::string c_str = tac->c ? tac->c->to_string() : "";
            if (b_str > c_str)
                std::swap(b_str, c_str);
            key = "+*:" + b_str + "," + c_str;
        }
        break;
    case TAC_OP::SUB:
        key = "-:" + (tac->b ? tac->b->to_string() : "") + "," + 
              (tac->c ? tac->c->to_string() : "");
        break;
    case TAC_OP::DIV:
        key = "/:" + (tac->b ? tac->b->to_string() : "") + "," + 
              (tac->c ? tac->c->to_string() : "");
        break;
    case TAC_OP::LT:
    case TAC_OP::LE:
    case TAC_OP::GT:
    case TAC_OP::GE:
    case TAC_OP::EQ:
    case TAC_OP::NE:
        key = std::to_string(static_cast<int>(tac->op)) + ":" +
              (tac->b ? tac->b->to_string() : "") + "," + 
              (tac->c ? tac->c->to_string() : "");
        break;
    default:
        return "";
    }
    
    return key;
}

// 公共子表达式消除（基本块内）
bool TACOptimizer::common_subexpression_elimination(std::shared_ptr<BasicBlock> block)
{
    bool changed = false;
    
    // 表达式 -> 结果变量的映射
    std::unordered_map<std::string, std::shared_ptr<SYM>> expr_map;
    
    auto tac = block->start;
    while (tac)
    {
        std::string key = get_expression_key(tac);
        
        if (!key.empty() && tac->a && tac->a->type == SYM_TYPE::VAR)
        {
            auto it = expr_map.find(key);
            if (it != expr_map.end())
            {
                // 找到相同的表达式，替换为拷贝
                tac->op = TAC_OP::COPY;
                tac->b = it->second;    //it->second 是临时变量的符号
                tac->c = nullptr;
                changed = true;
            }
            else
            {
                // 记录新表达式
                expr_map[key] = tac->a;
            }
        }
        
        // 如果有变量被重新定值，使相关表达式失效
        auto def = tac->get_def();
        if (def)
        {
            // 移除包含该变量的表达式
            std::vector<std::string> to_remove;
            for (auto& [expr_key, var] : expr_map)
            {
                if (expr_key.find(def->to_string()) != std::string::npos)
                {
                    to_remove.push_back(expr_key);
                }
            }
            for (const auto& key : to_remove)
            {
                expr_map.erase(key);
            }
        }
        
        if (tac == block->end)
            break;
        tac = tac->next;
    }
    
    return changed;
}

// 循环不变量外提
bool TACOptimizer::loop_invariant_code_motion(std::shared_ptr<BasicBlock> loop_header)
{
    bool changed = false;

    std::unordered_set<std::shared_ptr<BasicBlock>> loop_blocks;
    find_loop_blocks(loop_header, loop_blocks);

    if (loop_blocks.size() <= 1)
        return false;

    std::vector<std::shared_ptr<TAC>> loop_instructions;
    std::unordered_map<std::shared_ptr<TAC>, std::shared_ptr<BasicBlock>> instr_block;
    std::unordered_map<std::string, std::vector<std::shared_ptr<TAC>>> defs_in_loop;
    std::unordered_map<std::string, std::shared_ptr<TAC>> var_decl_in_loop;

    auto record_instruction = [&](std::shared_ptr<BasicBlock> block, std::shared_ptr<TAC> tac) {
        instr_block[tac] = block;
        loop_instructions.push_back(tac);

        if (tac->op == TAC_OP::VAR && tac->a && tac->a->type == SYM_TYPE::VAR)
        {
            var_decl_in_loop[tac->a->name] = tac;
        }

        auto def = tac->get_def();
        if (def)
        {
            defs_in_loop[def->name].push_back(tac);
        }
    };

    for (auto& block : loop_blocks)
    {
        if (!block || block == loop_header || !block->start || !block->end)
            continue;

        auto tac = block->start;
        while (tac)
        {
            record_instruction(block, tac);
            if (tac == block->end)
                break;
            tac = tac->next;
        }
    }

    if (loop_instructions.empty())
        return false;

    auto is_supported_op = [](TAC_OP op) {
        switch (op)
        {
        case TAC_OP::ADD:
        case TAC_OP::SUB:
        case TAC_OP::MUL:
        case TAC_OP::DIV:
        case TAC_OP::LT:
        case TAC_OP::LE:
        case TAC_OP::GT:
        case TAC_OP::GE:
        case TAC_OP::EQ:
        case TAC_OP::NE:
        case TAC_OP::COPY:
            return true;
        default:
            return false;
        }
    };

    auto operand_ready = [&](const std::shared_ptr<SYM>& sym,
                             const std::unordered_set<std::shared_ptr<TAC>>& movable) -> bool {
        if (!sym)
            return true;

        if (sym->type == SYM_TYPE::CONST_INT || sym->type == SYM_TYPE::CONST_CHAR)
            return true;

        if (sym->type != SYM_TYPE::VAR)
            return false;

        auto it = defs_in_loop.find(sym->name);
        if (it == defs_in_loop.end())
            return true; // 定义在循环外

        for (auto& defining_instr : it->second)
        {
            if (movable.find(defining_instr) == movable.end())
                return false;
        }

        return true;
    };

    std::unordered_set<std::shared_ptr<TAC>> movable;
    bool progress = true;
    while (progress)
    {
        progress = false;

        for (auto& instr : loop_instructions)
        {
            if (movable.find(instr) != movable.end())
                continue;

            if (!is_supported_op(instr->op))
                continue;

            auto def = instr->get_def();
            if (!def)
                continue;

            auto def_it = defs_in_loop.find(def->name);
            if (def_it == defs_in_loop.end())
                continue;

            if (def_it->second.size() != 1)
                continue; // 在循环中有多次定值，不能外提

            if (!operand_ready(instr->b, movable))
                continue;

            if (!operand_ready(instr->c, movable))
                continue;

            movable.insert(instr);
            progress = true;
        }
    }

    if (movable.empty())
        return false;

    std::shared_ptr<BasicBlock> preheader = nullptr;
    for (auto& pred : loop_header->predecessors)
    {
        if (loop_blocks.find(pred) == loop_blocks.end())
        {
            preheader = pred;
            break;
        }
    }

    if (!preheader || !preheader->end)
        return false;

    std::vector<std::shared_ptr<TAC>> ordered_to_move;
    ordered_to_move.reserve(movable.size());
    for (auto& instr : loop_instructions)
    {
        if (movable.find(instr) != movable.end())
            ordered_to_move.push_back(instr);
    }

    std::unordered_set<std::string> moved_var_decls;

    auto remove_from_block = [&](std::shared_ptr<TAC> node) {
        if (!node)
            return;

        auto block_it = instr_block.find(node);
        if (block_it == instr_block.end())
            return;

        auto block = block_it->second;
        if (!block)
            return;

        if (node == block->start)
            block->start = node->next;
        if (node == block->end)
            block->end = node->prev;

        if (node->prev)
            node->prev->next = node->next;
        if (node->next)
            node->next->prev = node->prev;

        node->prev = nullptr;
        node->next = nullptr;

        if (!block->start)
            block->start = block->end;
    };

    auto insert_after = [&](std::shared_ptr<TAC> node, std::shared_ptr<TAC> position) {
        if (!node || !position)
            return;

        node->prev = position;
        node->next = position->next;

        if (position->next)
            position->next->prev = node;
        position->next = node;

        if (preheader->end == position)
            preheader->end = node;

        instr_block[node] = preheader;
    };

    auto insertion_point = preheader->end;

    for (auto& instr : ordered_to_move)
    {
        auto def = instr->get_def();
        if (def)
        {
            auto decl_it = var_decl_in_loop.find(def->name);
            if (decl_it != var_decl_in_loop.end() &&
                moved_var_decls.insert(def->name).second)
            {
                auto decl = decl_it->second;
                remove_from_block(decl);
                insert_after(decl, insertion_point);
                insertion_point = decl;  // Update insertion point to maintain order
                changed = true;
            }
        }

        remove_from_block(instr);
        insert_after(instr, insertion_point);
        insertion_point = instr;  // Update insertion point to maintain order
        changed = true;
    }

    if (changed)
    {
        std::clog << "    Loop invariant code motion: found "
                  << ordered_to_move.size() << " invariant instructions" << std::endl;
    }

    return changed;
}

// 控制流简化：处理常量条件的分支
bool TACOptimizer::simplify_control_flow(std::shared_ptr<TAC> tac_start)
{
    bool changed = false;
    auto current = tac_start;
    
    while (current)
    {
        // 查找 IFZ 指令
        if (current->op == TAC_OP::IFZ && current->b)
        {
            int cond_value;
            if (current->b->get_const_value( cond_value))
            {
                // 条件是常量
                if (cond_value == 0)
                {
                    // ifz 0 goto L -> 总是跳转，转换为 goto L
                    current->op = TAC_OP::GOTO;
                    current->b = nullptr;
                    current->c = nullptr;
                    changed = true;
                    std::clog << "    Simplified: ifz 0 -> goto " << current->a->to_string() << std::endl;
                }
                else
                {
                    // ifz <非0> goto L -> 永不跳转，删除此指令
                    std::clog << "    Simplified: ifz " << cond_value << " -> removed (never jumps)" << std::endl;
                    
                    auto next = current->next;
                    auto prev = current->prev;
                    
                    // 删除该指令
                    if (prev)
                        prev->next = next;
                    if (next)
                        next->prev = prev;
                    
                    // 清空链接
                    current->prev = nullptr;
                    current->next = nullptr;
                    
                    current = next;
                    changed = true;
                    continue;
                }
            }
        }
        // 查找连续的 GOTO 指令
        else if (current->op == TAC_OP::GOTO && current->next && 
                 current->next->op == TAC_OP::LABEL)
        {
            // goto L; label L; -> 可以删除 goto
            if (current->a && current->next->a && 
                current->a->name == current->next->a->name)
            {
                std::clog << "    Removed redundant goto to next label" << std::endl;
                
                auto next = current->next;
                auto prev = current->prev;
                
                if (prev)
                    prev->next = next;
                if (next)
                    next->prev = prev;
                
                // 清空链接
                current->prev = nullptr;
                current->next = nullptr;
                
                current = next;
                changed = true;
                continue;
            }
        }
        
        current = current->next;
    }
    
    return changed;
}

// 不可达代码消除：删除永远不会执行的代码块
bool TACOptimizer::eliminate_unreachable_code(std::vector<std::shared_ptr<BasicBlock>>& blocks)
{
    bool changed = false;
    
    if (blocks.empty())
        return false;
    
    // 使用可达性分析
    std::unordered_set<std::shared_ptr<BasicBlock>> reachable;
    std::queue<std::shared_ptr<BasicBlock>> worklist;
    
    // 从第一个块开始（程序入口，多函数由于不启用优化，可认为block 0为入口）
    worklist.push(blocks[0]);
    reachable.insert(blocks[0]);
    
    while (!worklist.empty())
    {
        auto block = worklist.front();
        worklist.pop();
        
        for (auto& succ : block->successors)
        {
            if (reachable.find(succ) == reachable.end())
            {
                reachable.insert(succ);
                worklist.push(succ);
            }
        }
    }
    
    // 删除不可达的块
    std::vector<std::shared_ptr<BasicBlock>> new_blocks;
    for (auto& block : blocks)
    {
        if (reachable.find(block) != reachable.end())
        {
            new_blocks.push_back(block);
        }
        else
        {
            std::clog << "    Removing unreachable block " << block->id << std::endl;
            
            // 从 TAC 链表中删除该块的所有指令
            auto tac = block->start;
            while (tac)
            {
                auto next = (tac == block->end) ? nullptr : tac->next;
                auto prev = tac->prev;
                auto curr_next = tac->next;
                
                if (prev)
                    prev->next = curr_next;
                if (curr_next)
                    curr_next->prev = prev;
                
                // 清空被删除指令的链接
                tac->prev = nullptr;
                tac->next = nullptr;
                
                tac = next;
                if (!next)
                    break;
            }
            
            changed = true;
        }
    }
    
    if (changed)
    {
        blocks = new_blocks;
    }
    
    return changed;
}

// 消除未使用的变量声明（该方法不适用于多函数，因为没有考虑函数作用域和参数传递）
bool TACOptimizer::eliminate_unused_var_declarations(std::shared_ptr<TAC> tac_start)
{
    bool changed = false;
    
    // 收集所有被使用的变量（除了声明）
    std::unordered_set<std::string> used_vars;
    
    auto current = tac_start;
    while (current)
    {
        // 跳过 VAR 声明，收集其他地方使用的变量
        if (current->op != TAC_OP::VAR)
        {
            if (current->a && current->a->type == SYM_TYPE::VAR)
                used_vars.insert(current->a->name);
            if (current->b && current->b->type == SYM_TYPE::VAR)
                used_vars.insert(current->b->name);
            if (current->c && current->c->type == SYM_TYPE::VAR)
                used_vars.insert(current->c->name);
        }
        
        current = current->next;
    }
    
    // 删除未使用的 VAR 声明
    current = tac_start;
    while (current)
    {
        auto next = current->next;
        
        if (current->op == TAC_OP::VAR && current->a && current->a->type == SYM_TYPE::VAR)
        {
            // 检查该变量是否被使用
            if (used_vars.find(current->a->name) == used_vars.end())
            {
                std::clog << "    Removing unused var declaration: " << current->a->name << std::endl;
                
                auto prev = current->prev;
                auto curr_next = current->next;
                
                // 删除该声明
                if (prev)
                    prev->next = curr_next;
                if (curr_next)
                    curr_next->prev = prev;
                
                // 清空链接
                current->prev = nullptr;
                current->next = nullptr;
                
                changed = true;
            }
        }
        
        current = next;
    }
    
    return changed;
}

void TACOptimizer::optimize()
{
    // 构建控制流图
    block_builder.build();
    block_builder.print_basic_blocks(std::clog);
    auto blocks = block_builder.get_basic_blocks();
    
    if (blocks.empty())
        return;
    
    // 多轮迭代优化
    bool global_changed = true;
    int global_iter = 0;
    const int MAX_GLOBAL_ITER = 20;
    
    while (global_changed && global_iter < MAX_GLOBAL_ITER)
    {
        global_changed = false;
        global_iter++;
        
        std::clog << "\n=== Optimization Pass " << global_iter << " ===" << std::endl;

        //局部优化（基本块内）
        for (auto& block : blocks)
        {
            optimize_block_local(block);
        }
        
        // 公共子表达式消除（每个基本块内）
        for (auto& block : blocks)
        {
            if (common_subexpression_elimination(block))
            {
                global_changed = true;
                std::clog << "  - CSE applied in block " << block->id << std::endl;
            }
        }
        
        // 循环不变量外提
        for (auto& block : blocks)
        {
            if (is_loop_header(block))
            {
                if (loop_invariant_code_motion(block))
                {
                    global_changed = true;
                    std::clog << "  - LICM applied for loop at block " << block->id << std::endl;
                }
            }
        }
        
        // 数据流分析
        block_builder.compute_data_flow();
        
        // 全局优化
        if (global_constant_propagation(blocks))
        {
            global_changed = true;
            std::clog << "  - Global constant propagation applied" << std::endl;
        }
        
        // 再次进行局部常量折叠（处理新产生的常量）
        for (auto& block : blocks)
        {
            if (local_constant_folding(block->start,block->end))
            {
                global_changed = true;
            }
        }
        
        //消除未使用的变量声明
        if (global_dead_code_elimination(blocks))
        {
            global_changed = true;
            std::clog << "  - Dead code elimination applied" << std::endl;

            block_builder.build();
            blocks = block_builder.get_basic_blocks();
        }
        
        // 控制流简化
        if (simplify_control_flow(tac_first))
        {
            global_changed = true;
            std::clog << "  - Control flow simplification applied" << std::endl;

            block_builder.build();
            blocks = block_builder.get_basic_blocks();
        }
        
        // 不可达代码消除
        if (eliminate_unreachable_code(blocks))
        {
            global_changed = true;
            std::clog << "  - Unreachable code elimination applied" << std::endl;

            block_builder.build();
            blocks = block_builder.get_basic_blocks();
        }
    }
    
    // 最后一轮清理：删除未使用的变量声明（包括临时变量）
    if (eliminate_unused_var_declarations(tac_first))
    {
        std::clog << "  - Unused variable declarations eliminated" << std::endl;
    }
    
    std::clog << "\n=== Optimization completed in " << global_iter << " passes ===" << std::endl;
}